package 贪心;


import javax.swing.*;
import java.util.Arrays;

public class 贪心7_k次取反后的最大化数组和 {

    public int largestSumAfterKNegations(int[] nums, int k) {
        int sum=0;
        //1.按我们的贪心策略，就是要把所有负数全部变成正数，所以一开始我们就得找到负数的个数，好方便使用这k次来处理
        int negativeCount = 0;
        for (int i = 0; i < nums.length; i++) {
            if(nums[i]<0)negativeCount++;//要注意negativeCount为0或者未nums.length的时候
        }
        //2.排序一下，然后尽可能把最小的负数都变成正数
        Arrays.sort(nums);
        if(k<=negativeCount){
            for(int i=0;i<k;i++){
                nums[i]=-nums[i];
            }
        }else{
            for(int i=0;i<negativeCount;i++){
                nums[i]=-nums[i];
            }
            k-=negativeCount;
            if(k%2==1){
                int Min=Math.min(negativeCount-1>=0?nums[negativeCount-1]: nums[0],negativeCount<nums.length?nums[negativeCount]:nums[nums.length-1]);
                sum-=2*Min;
            }
        }

        //3.求和
        for (int i = 0; i < nums.length; i++) {
            sum+=nums[i];
        }
        return sum;
    }

    public static void main(String[] args) {
        System.out.println(new 贪心7_k次取反后的最大化数组和().largestSumAfterKNegations(new int[]{2,-3,-1,5,-4},2));

    }

}
